package class5;

import common.TreeNode;
import common.TreeNodeUtils;

/**
 * https://leetcode.cn/problems/validate-binary-search-tree/description/
 * 搜索二叉树
 * *      5
 * *    /   \
 * *   3     8
 * *  2 4   7 9
 * * 1     6   10
 * 1.process(5,-9999,9999);
 * 3.process(3,-9999,5);
 * 2.process(2,-9999,3);
 * 1.process(1,-9999,2);
 * 4.process(4,-9999,5);
 * <p>
 * 8.process(8,5,9999);
 * 7.process(7,5,8);
 * 6.process(6,5,7);
 * 9.process(9,8,9999);
 * 10.process(10,9,9999);
 */
public class Code08_isBinarySearchTree_01 {

    public static void main(String[] args) {
        TreeNode searchTree = TreeNodeUtils.getBinarySearchTree();
        boolean bst = isBST(searchTree);
        System.out.println("bst = " + bst);
    }

    public static boolean isBST(TreeNode treeNode) {
        return process(treeNode, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public static boolean process(TreeNode treeNode, long min, long max) {
        if (treeNode == null) {
            return true;
        }
        /**
         * 每个节点的值必须满足：min < treeNode.val < max，
         * 并且其左右子树的值也要分别满足对应的范围约束。
         */
        if (treeNode.val <= min || treeNode.val >= max) {// 当节点小于限制最小值，或大于最大值
            return false;
        }
        // 子节点最小值和最大值
        boolean isBST_L = process(treeNode.left, min, treeNode.val);
        boolean isBST_R = process(treeNode.right, treeNode.val, max);
        return isBST_L && isBST_R;
    }

}


